#include <iostream>
#include <vector>
#include <algorithm>

using std::cout;
using std::swap;
using std::vector;


void shellSort(vector<int>& v)
{
    for(int gap = v.size() / 2;gap >= 1;gap /= 2)
    {
        // 要和前比较的节点
        for(int i = gap;i < v.size(); ++ i)
        {
            // 真正意义上的插入
            for(int j = i;j >= gap && v[j] < v[j - gap];j -= gap)
            {
                swap(v[j],v[j - gap]);
            }
        }
    }
}


int main(int argc, char const *argv[])
{
    vector<int> v({5, 2, 6, 67, 7, 4, 3, 6, 9, 44, 32});

    shellSort(v);
    // vector<int> rst = quickSort(v, 0, v.size() - 1);
    for (auto &num : v)
    {
        cout << num << " ";
    }
    cout << "\n";
    getchar();
    return 0;
}
